{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #判断是否为平衡二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isBalanced"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #判断是否为平衡二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,9,20,null,null,15,7]\n",
    "<strong>输出：</strong>true \n",
    "<strong>解释：</strong>如下图\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode.cn/1695102431-vbmWJn-image.png\" style=\"height: 281px; width: 500px;\" /><br />\n",
    "<br />\n",
    "<strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "输入：root = [1,2,2,3,3,null,null,4,4]\n",
    "输出：false\n",
    "解释：如下图\n",
    "</pre>\n",
    "<img alt=\"\" src=\"https://pic.leetcode.cn/1695102434-WlaxCo-image.png\" style=\"height: 281px; width: 500px;\" />\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= 树的结点个数 &lt;= 10000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 110&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/balanced-binary-tree/\">https://leetcode-cn.com/problems/balanced-binary-tree/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ping-heng-er-cha-shu-lcof](https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ping-heng-er-cha-shu-lcof](https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root: return True\n",
    "        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \\\n",
    "            self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n",
    "    def depth(self, root):\n",
    "        if not root: return 0\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        n = 0\n",
    "        while queue:\n",
    "            n += 1\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root: return True\n",
    "        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \\\n",
    "            self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n",
    "    def depth(self, root):\n",
    "        if not root: return 0\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        n = 0\n",
    "        while queue:\n",
    "            n += 1\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        left = self.cal_height1(root.left)\n",
    "        right = self.cal_height1(root.right)\n",
    "        if abs(left - right) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "        \n",
    "    def cal_height(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        left_height = self.cal_height(root.left)\n",
    "        right_height = self.cal_height(root.right)\n",
    "        return max(left_height, right_height) + 1\n",
    "\n",
    "    def cal_height1(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        queue = [root]\n",
    "        depth = 0\n",
    "        while queue:\n",
    "            l_q = len(queue)\n",
    "            for i in range(l_q):\n",
    "                node = queue.pop(0)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            depth += 1\n",
    "        return depth \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def getTreeHeight(self, node: TreeNode):\n",
    "        ans = 0\n",
    "        if not node:\n",
    "            return ans\n",
    "        q = Queue()\n",
    "        q.put(node)\n",
    "\n",
    "        while not q.empty():\n",
    "            n = q.qsize()\n",
    "            for _ in range(n):\n",
    "                node = q.get()\n",
    "                if node.left:\n",
    "                    q.put(node.left)\n",
    "                if node.right:\n",
    "                    q.put(node.right)\n",
    "            ans += 1\n",
    "        return ans\n",
    "\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        def dfs(node: TreeNode):\n",
    "            if not node:\n",
    "                return True\n",
    "            result = abs(self.getTreeHeight(node.left) - self.getTreeHeight(node.right)) <= 1\n",
    "            return result and dfs(node.left) and dfs(node.right)\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        trees = [root]\n",
    "        t = 0\n",
    "        while trees != []:\n",
    "            t += 1\n",
    "            tree = []\n",
    "            for i in trees:\n",
    "                if i.left:\n",
    "                    tree.append(i.left)\n",
    "                if i.right:\n",
    "                    tree.append(i.right)\n",
    "            trees = tree\n",
    "        return t\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        roots = [root]\n",
    "        def dfs(root):\n",
    "            l = self.maxDepth(root.left)\n",
    "            r = self.maxDepth(root.right)\n",
    "            a = l - r\n",
    "            if a not in [-1,0,1]:\n",
    "                return False\n",
    "            else:\n",
    "                if root.left:\n",
    "                    roots.append(root.left)\n",
    "                if root.right:\n",
    "                    roots.append(root.right)\n",
    "                return True\n",
    "        for i in roots:\n",
    "            if not dfs(i):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def get_depth(node: TreeNode):\n",
    "            if not node: return 0\n",
    "\n",
    "            queue = deque()\n",
    "            queue.append(node)\n",
    "            level = 0\n",
    "            while c := len(queue):\n",
    "                i = 0\n",
    "                while i < c:\n",
    "                    node_ = queue.popleft()\n",
    "                    if node_.left: queue.append(node_.left)\n",
    "                    if node_.right: queue.append(node_.right)\n",
    "                    i += 1\n",
    "                level += 1\n",
    "            return level\n",
    "        \n",
    "        def mytraverse(node: TreeNode):\n",
    "            if not node or (not node.left and not node.right): return True\n",
    "            if -1 <= get_depth(node.left) - get_depth(node.right) <= 1:\n",
    "                return mytraverse(node.left) and mytraverse(node.right)\n",
    "            else: return False\n",
    "\n",
    "        return mytraverse(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def maxDepth(root):\n",
    "            if not root: return 0\n",
    "            stack = [(root, root.val, 1)]\n",
    "            res = []\n",
    "            while stack:\n",
    "                node, val, temp = stack.pop()\n",
    "                if not node.left and not node.right : res.append(temp)\n",
    "                if node.left:\n",
    "                    stack.append((node.left, val+node.left.val, temp + 1))\n",
    "                if node.right:\n",
    "                    stack.append((node.right, val+node.right.val, temp + 1))\n",
    "            return max(res)\n",
    "        if not root: return True\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "            res.append(abs(maxDepth(node.left)-maxDepth(node.right)))\n",
    "        for i in res:\n",
    "            if i < -1 or i >1:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    # def maxDepth(root):\n",
    "    #     if not root: return 0\n",
    "    #     stack = [(root, root.val, 1)]\n",
    "    #     res = []\n",
    "    #     while stack:\n",
    "    #         node, val, temp = stack.pop()\n",
    "    #         if not node.left and not node.right : res.append(temp)\n",
    "    #         if node.left:\n",
    "    #             stack.append((node.left, val+node.left.val, temp + 1))\n",
    "    #         if node.right:\n",
    "    #             stack.append((node.right, val+node.right.val, temp + 1))\n",
    "    #     return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "        if abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \\\n",
    "            self.isBalanced(root.left) and self.isBalanced(root.right):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n",
    "    def depth(self, root):\n",
    "        if not root: return 0\n",
    "        return max(self.depth(root.left), self.depth(root.right)) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        head = root\n",
    "        if head == None:\n",
    "            return True\n",
    "        node_list = []\n",
    "        node_list.append([head,0,0,0])\n",
    "        res = []\n",
    "        for i in range(100000):\n",
    "            head, flag, dl, dr = node_list[-1]\n",
    "            if head.left:\n",
    "                if node_list[-1][1]==0:\n",
    "                    node_list.append([head.left, 0,0,0])\n",
    "                    continue\n",
    "            else:\n",
    "                node_list[-1][2] = 0                \n",
    "            node_list[-1][1] = max(1, node_list[-1][1])\n",
    "\n",
    "            if head.right :\n",
    "                if node_list[-1][1]==1:\n",
    "                    node_list.append([head.right, 0,0,0])\n",
    "                    continue\n",
    "            else:\n",
    "                node_list[-1][3] = 0\n",
    "            node_list[-1][1] = max(1, node_list[-1][1])\n",
    "\n",
    "            if node_list[-1][2]-node_list[-1][3] > 1 or node_list[-1][2]-node_list[-1][3] < -1:\n",
    "                return False\n",
    "            dep = max(node_list[-1][2], node_list[-1][3])\n",
    "\n",
    "            if node_list.__len__() == 1:\n",
    "                break\n",
    "            node_list.pop()\n",
    "            node_list[-1][1] += 1\n",
    "            if head == node_list[-1][0].left:\n",
    "                node_list[-1][2] = dep+1\n",
    "            if head == node_list[-1][0].right:\n",
    "                node_list[-1][3] = dep+1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:return 0\n",
    "        return max(self.maxDepth(root.left)+1,self.maxDepth(root.right)+1)\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:return True\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right) and abs(self.maxDepth(root.right)-self.maxDepth(root.left))<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.balance = True\n",
    "    def depth(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        return max(1 + self.depth(root.left), 1 + self.depth(root.right))\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if root.left:\n",
    "            self.isBalanced(root.left)\n",
    "        if root.right:\n",
    "            self.isBalanced(root.right)\n",
    "        leftDepth = self.depth(root.left)\n",
    "        rightDepth = self.depth(root.right)\n",
    "        print(root.val, leftDepth, rightDepth)\n",
    "        if abs(leftDepth - rightDepth) > 1:\n",
    "            self.balance = False\n",
    "        return self.balance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def depth(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.depth(root.left),self.depth(root.right))+1\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        left = self.depth(root.left)\n",
    "        right = self.depth(root.right)\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right) and abs(left-right)<=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root):\n",
    "        if root is None:\n",
    "            return 0, True\n",
    "        else:\n",
    "            ld, lf = self.dfs(root.left)\n",
    "            if not lf:\n",
    "                return 0, False\n",
    "            rd, rf = self.dfs(root.right)\n",
    "            if not rf:\n",
    "                return 0, False\n",
    "            return max(ld, rd)+1, -1<=ld-rd<=1\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        _, flag = self.dfs(root)\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        res = True\n",
    "        if not root:\n",
    "            return True\n",
    "        if not self.isBalanced(root.left) or not self.isBalanced(root.right):\n",
    "            res = False\n",
    "        gap = abs(self.maxDepth(root.left) - self.maxDepth(root.right))\n",
    "        if gap > 1:\n",
    "            res = False\n",
    "        return res\n",
    "        \n",
    "\n",
    "    \n",
    "    def maxDepth(self,root:TreeNode):\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = self.maxDepth(root.left)\n",
    "        right = self.maxDepth(root.right)\n",
    "        return max(left,right) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # 递归定义，就递归判断左右子树的深度是不是相差小于1\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def recur(root: TreeNode) -> int:\n",
    "            if root == None: return 0\n",
    "            left = recur(root.left)\n",
    "            if left == -1: return -1\n",
    "            right = recur(root.right)\n",
    "            if right == -1: return -1\n",
    "            return max(left, right)+1 if abs(left - right) <= 1 else -1\n",
    "        \n",
    "        return recur(root) != -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:            \n",
    "        if root==None:\n",
    "            return True\n",
    "        left_h = self.hight(root.left)\n",
    "        right_h = self.hight(root.right)\n",
    "        isL = self.isBalanced(root.left)\n",
    "        isR = self.isBalanced(root.right)\n",
    "\n",
    "        return abs(left_h-right_h)<=1 and isL and isR\n",
    "    def hight(self,root):\n",
    "        if root==None:\n",
    "            return 0\n",
    "        return  max(self.hight(root.left),self.hight(root.right))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if root == None:\n",
    "            return True\n",
    "        ldepth = Solution().treeHeight(root.left)\n",
    "        rdepth = Solution().treeHeight(root.right)\n",
    "\n",
    "        left = Solution.isBalanced(self,root.left)\n",
    "        if abs(ldepth - rdepth) > 1:\n",
    "            return False\n",
    "        right = Solution.isBalanced(self,root.right)\n",
    "        if abs(ldepth - rdepth) > 1:\n",
    "            return False\n",
    "        return right and left\n",
    "\n",
    "    def treeHeight(self, root):\n",
    "        if root == None:\n",
    "            return 0\n",
    "        ldepth  = Solution().treeHeight(root.left)\n",
    "        rdepth = Solution().treeHeight(root.right)\n",
    "        return max(ldepth,rdepth)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # 获取有几层\n",
    "    def cengxu(self, root):\n",
    "        depth = 0\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "\n",
    "        while queue!=[]:\n",
    "            depth +=1\n",
    "\n",
    "            tmp_queue = []\n",
    "            while queue!=[]:\n",
    "                tmp_queue.append(queue.pop(0))\n",
    "\n",
    "            while tmp_queue!=[]:\n",
    "                node = tmp_queue.pop(-1)\n",
    "                if node.left!=None:\n",
    "                    queue.append(node.left)\n",
    "                if node.right !=None:\n",
    "                    queue.append(node.right)\n",
    "            #print(self.depth)\n",
    "        return depth\n",
    "\n",
    "    def check_balanced(self,root):\n",
    "        \n",
    "        # 先判断孩子节点是否平衡 \n",
    "        # 如果没有左右节点 则说明是平衡的 因为下面没有对应的孩子不会进if 所以默认初始是 True\n",
    "\n",
    "        is_left_balance = True\n",
    "        is_right_balance = True\n",
    "\n",
    "        if root.left!= None:\n",
    "            is_left_balance = self.check_balanced(root.left)\n",
    "        if root.right!= None:\n",
    "            is_right_balance = self.check_balanced(root.right)\n",
    "\n",
    "        # #  \n",
    "        # if root.left == None and root.right == None:\n",
    "        #     is_left_balance = True\n",
    "        #     is_right_balance = True\n",
    "\n",
    "        # 再判断当前节点平衡否\n",
    "        left_depth = 0\n",
    "        right_depth = 0\n",
    "        \n",
    "        if root.left!= None:\n",
    "            left_depth = self.cengxu(root.left)\n",
    "        if root.right != None:\n",
    "            right_depth = self.cengxu(root.right)\n",
    "\n",
    "        \n",
    "        is_dangqian_balance = False\n",
    "        if abs(left_depth-right_depth) <= 1:\n",
    "            is_dangqian_balance = True\n",
    "\n",
    "        print(left_depth,right_depth)\n",
    "\n",
    "\n",
    "        if is_left_balance==True and is_right_balance == True and is_dangqian_balance == True:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        #root = TreeNode(1)\n",
    "        #root.left = TreeNode(2)\n",
    "        if root == None:return True\n",
    "        return self.check_balanced(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def get_depth(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = get_depth(node.left)\n",
    "            right = get_depth(node.right)\n",
    "            if left == -1 or right == -1:\n",
    "                return -1\n",
    "            if abs(left-right) <= 1:\n",
    "                return max(left, right)+1\n",
    "            else:\n",
    "                return -1\n",
    "        return get_depth(root) != -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l = helper(root.left)\n",
    "            r = helper(root.right)\n",
    "            if abs(l-r) <= 1:\n",
    "                return max(l, r) + 1\n",
    "            else:\n",
    "                return float('inf')\n",
    "        return helper(root) != float('inf')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        def nodeDept(node: TreeNode):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return max(nodeDept(node.left), nodeDept(node.right)) + 1\n",
    "        return abs(nodeDept(root.left) - nodeDept(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def deepth(root):\n",
    "            if not root: return 0\n",
    "            return 1+max(deepth(root.left),deepth(root.right))\n",
    "        if not root: return  True\n",
    "        return abs(deepth(root.left) - deepth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def recur(root):\n",
    "            if not root: return 0\n",
    "            left = recur(root.left)\n",
    "            if left == -1: return -1\n",
    "            right = recur(root.right)\n",
    "            if right == -1: return -1\n",
    "            return max(left, right) + 1 if abs(left - right) <= 1 else -1\n",
    "\n",
    "        return recur(root) != -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def recur(root):\n",
    "            if not root: return 0\n",
    "            left = recur(root.left)\n",
    "            if left == -1: return -1\n",
    "            right = recur(root.right)\n",
    "            if right == -1: return -1\n",
    "            return max(left,right) + 1 if abs(left-right) <= 1 else -1\n",
    "        return recur(root) != -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "        def recur(node):\n",
    "            if not node: return 0\n",
    "            left = recur(node.left)\n",
    "            right = recur(node.right)\n",
    "            if left == -1 or right == -1: return -1\n",
    "            if abs(left - right) > 1: \n",
    "                return -1\n",
    "            else:\n",
    "                return max(left, right) + 1\n",
    "        return recur(root) != -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \\\n",
    "            self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n",
    "    def depth(self, root):\n",
    "        if not root: return 0\n",
    "        return max(self.depth(root.left), self.depth(root.right)) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        delta = self.maxDepth(root.left) - self.maxDepth(root.right)\n",
    "\n",
    "        return abs(delta) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n",
    "\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        \n",
    "        if root == None:\n",
    "            return 0\n",
    "\n",
    "        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "        return abs(self.helper(root.left) - self.helper(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "    \n",
    "    def helper(self, root):\n",
    "        if not root: return 0\n",
    "        return max(self.helper(root.left), self.helper(root.right)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        return False if self.travel(root) == -1 else True\n",
    "    \n",
    "    def travel(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        l = self.travel(root.left)\n",
    "        r = self.travel(root.right)\n",
    "        if l == -1 or r == -1:\n",
    "            return -1\n",
    "        if l - r > 1 or l - r < -1:\n",
    "            return -1\n",
    "        return max(l, r)+1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            left_depth = self.maxDepth(node.left)\n",
    "            right_depth = self.maxDepth(node.right)\n",
    "            if abs(left_depth - right_depth)>1:\n",
    "                return False\n",
    "            if node.left: queue.append(node.left)\n",
    "            if node.right: queue.append(node.right)\n",
    "        return True\n",
    "        \n",
    "\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root: return 0\n",
    "        return max(self.maxDepth(root.left), self.maxDepth(root.right))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        return self.balanced(root)\n",
    "\n",
    "    def balanced(self, root):\n",
    "        if root == None:\n",
    "            return True\n",
    "        if not self.balanced(root.left):\n",
    "            return False\n",
    "        if not self.balanced(root.right):\n",
    "            return False\n",
    "        left, right = 0, 0\n",
    "        if root.left != None:\n",
    "            left = root.left.level\n",
    "        if root.right != None:\n",
    "            right = root.right.level\n",
    "        if abs(left - right) > 1:\n",
    "            return False\n",
    "        root.level = max(left,right) + 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(self.tree_len(root.left) - self.tree_len(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n",
    "    def tree_len(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.tree_len(root.left), self.tree_len(root.right)) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        return self.dps(root) >= 0\n",
    "    \n",
    "    def dps(self, node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        left = self.dps(node.left)\n",
    "        right = self.dps(node.right)\n",
    "        if left == -1 or right == -1 or abs(left-right) > 1:\n",
    "            return -1\n",
    "        else:\n",
    "            return max(left, right) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "        if self.get_depth(root) == -1: return False\n",
    "        else: return True\n",
    "    \n",
    "    def get_depth(self, root):\n",
    "        if not root: return 0\n",
    "        left_d = self.get_depth(root.left)\n",
    "        if left_d == -1: return -1\n",
    "        right_d = self.get_depth(root.right)\n",
    "        if right_d == -1: return -1\n",
    "        if abs(left_d - right_d) > 1: return -1\n",
    "        return max(left_d, right_d) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and self.isBalanced(\n",
    "            root.left) and self.isBalanced(root.right)\n",
    "\n",
    "    def depth(self, root):\n",
    "        if not root: return 0\n",
    "        return max(self.depth(root.left), self.depth(root.right)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        left_dep = self.depth(root.left)\n",
    "        right_dep = self.depth(root.right)\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right) and abs(left_dep - right_dep) <= 1\n",
    "    def depth(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            return max(self.depth(root.left), self.depth(root.right)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        _,flag=self.f(root)\n",
    "        return flag\n",
    "    def f(self,root):\n",
    "        l=root.left\n",
    "        r=root.right\n",
    "        ll=0\n",
    "        rr=0\n",
    "        fl=True\n",
    "        fr=True\n",
    "        if l:\n",
    "            ll,fl=self.f(l)\n",
    "        if r:\n",
    "            rr,fr=self.f(r)\n",
    "        flag=abs(ll-rr)<2\n",
    "        flag=flag and fl and fr\n",
    "        return max(ll,rr)+1,flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def depth(self,root: TreeNode)->int: #返回树的深度，-1表示非平衡二叉树\n",
    "        if not root :\n",
    "            return 0\n",
    "        \n",
    "        left = self.depth(root.left)\n",
    "        \n",
    "        if left==-1  :\n",
    "            return -1\n",
    "\n",
    "        right = self.depth(root.right)\n",
    "\n",
    "        if right ==-1 :\n",
    "            return -1\n",
    "\n",
    "        if abs(left-right)>1:\n",
    "            return -1\n",
    "        else:\n",
    "            return 1 + max( self.depth(root.left),self.depth(root.right))\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        return self.depth(root)!=-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root):\n",
    "        depth = 0\n",
    "        if root:\n",
    "            depthleft, bleft = self.dfs(root.left)\n",
    "            depthright, bright = self.dfs(root.right)\n",
    "            depth = max(depthleft, depthright) + 1\n",
    "            if abs(depthright - depthleft) <= 1 and bleft and bright:\n",
    "                return depth, True\n",
    "            else:\n",
    "                return depth, False\n",
    "        return depth, True\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        depth, b = self.dfs(root)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pro(self,root,depth):\n",
    "        if root == None:\n",
    "            return depth\n",
    "        a = self.pro(root.left,depth+1)\n",
    "        b = self.pro(root.right,depth+1)\n",
    "\n",
    "        if (abs(a - b) >1):\n",
    "            self.judge = self.judge and False\n",
    "        return max(a,b)\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "         self.judge = True\n",
    "         self.pro(root,0)\n",
    "         return  self.judge\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,node:TreeNode,d:int) ->(bool,int):\n",
    "        if not node:\n",
    "            return (True,d)\n",
    "        mdl = self.dfs(node.left,d+1)\n",
    "        if not mdl[0]:\n",
    "            return (False,0)\n",
    "        mdr = self.dfs(node.right,d+1)\n",
    "        return (mdl[0] and mdr[0] and abs(mdl[1]-mdr[1])<2,max(mdl[1],mdr[1]))\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        ret= self.dfs(root,0)\n",
    "        return ret[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if abs(self.dfs(root.left, 0) - self.dfs(root.right, 0)) <= 1:\n",
    "            return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def dfs(self, root, depth):\n",
    "        if not root:\n",
    "            return depth\n",
    "        return max(self.dfs(root.left, depth + 1), self.dfs(root.right, depth + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache()\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(self.tree_len(root.left) - self.tree_len(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n",
    "    def tree_len(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.tree_len(root.left), self.tree_len(root.right)) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def deep_tree(self, root: TreeNode):\n",
    "        if (root == None):\n",
    "            return 0\n",
    "        depth_left = self.deep_tree(root.left)\n",
    "        depth_right = self.deep_tree(root.right)\n",
    "        max_depth = max(depth_left + 1, depth_right + 1)\n",
    "        self.tree_dict[root] = max_depth\n",
    "        return max_depth\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def balence(self,left:TreeNode, right:TreeNode):\n",
    "        if (left == None and right == None):\n",
    "            return True\n",
    "\n",
    "        depth_left = self.tree_dict[left] if left is not None else 0\n",
    "        depth_right = self.tree_dict[right] if right is not None else 0\n",
    "        if(abs(depth_left - depth_right)>=2):\n",
    "            return False\n",
    "        if(left is not None):\n",
    "            ret = self.balence(left.left,left.right)\n",
    "            if(ret == False):\n",
    "                return False\n",
    "        if(right is not None):\n",
    "            ret = self.balence(right.left,right.right)\n",
    "            if(ret == False):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if(root == None):\n",
    "            return True\n",
    "        self.tree_dict = dict()\n",
    "        self.deep_tree(root)\n",
    "        ret = self.balence(root.left,root.right)\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        self.balance=True\n",
    "        def isBalanced_sub(self,root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            left_depth=isBalanced_sub(self,root.left)\n",
    "            right_depth=isBalanced_sub(self,root.right)\n",
    "            if abs(left_depth-right_depth)>1:\n",
    "                self.balance=False\n",
    "            return max(left_depth,right_depth)+1\n",
    "        isBalanced_sub(self,root)\n",
    "        return self.balance\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        \n",
    "        def treeDeep(root):\n",
    "            if not root: return 0\n",
    "            right = treeDeep(root.right)\n",
    "            if right == -1:\n",
    "                return -1\n",
    "            left = treeDeep(root.left)\n",
    "            if left == -1:\n",
    "                return -1\n",
    "            return -1 if abs(right - left) > 1 else max(right, left) + 1\n",
    "        return treeDeep(root) != -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def maxdepth(node):\n",
    "    if not node: return 0\n",
    "\n",
    "    return max(maxdepth(node.left), maxdepth(node.right))+1\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "\n",
    "        return abs(maxdepth(root.left) - maxdepth(root.right)) <= 1 and \\\n",
    "            self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#0     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    balance = True\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def Deepth(root: TreeNode,a)->int:\n",
    "            if not root :\n",
    "                return 0\n",
    "            else :\n",
    "                left = Deepth(root.left,a)\n",
    "                right = Deepth(root.right,a)\n",
    "                if abs(right - left) > 1:\n",
    "                    a['balance'] = False\n",
    "                return max(left,right)+1\n",
    "\n",
    "        a= {'balance':True}\n",
    "        Deepth(root,a)\n",
    "        return a['balance']\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def depth(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            left = depth(root.left)\n",
    "            right = depth(root.right)\n",
    "            return max(left,right)+1\n",
    "        if root is None:\n",
    "            return True\n",
    "        return abs(depth(root.left)-depth(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left), height(root.right))+1\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def recur(root):\n",
    "            if not root:return 0\n",
    "            leftheight = recur(root.left)\n",
    "            if leftheight == -1:return -1\n",
    "            rightheight = recur(root.right)\n",
    "            if rightheight == -1:return -1\n",
    "            if abs(leftheight - rightheight) > 1:\n",
    "                return -1\n",
    "            else:\n",
    "                return max(leftheight,rightheight) + 1\n",
    "        return recur(root) != -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        self.n = 0\n",
    "        self.max_gap = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            self.n += 1\n",
    "            n1 = self.n\n",
    "            n2 = self.n\n",
    "            if node.left:\n",
    "                n1 = dfs(node.left)\n",
    "                self.n -= 1\n",
    "            if node.right:\n",
    "                n2 = dfs(node.right)\n",
    "                self.n -= 1\n",
    "            self.max_gap = abs(n2-n1) if abs(n2-n1)>self.max_gap else self.max_gap\n",
    "            return max([n1, n2])\n",
    "            \n",
    "\n",
    "        dfs(root)\n",
    "        if self.max_gap > 1:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def get_height(node):\n",
    "            if not node: return 0\n",
    "            l_height = get_height(node.left)\n",
    "            r_height = get_height(node.right)\n",
    "            if l_height == -1 or r_height==-1 or abs(l_height - r_height) > 1:\n",
    "                return -1\n",
    "            else:\n",
    "                return max(l_height, r_height) + 1\n",
    "        return get_height(root) >= 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced_(self, root: TreeNode) -> bool:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return 1 + max(dfs(node.left), dfs(node.right))\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        return abs( dfs(root.left) - dfs(root.right) ) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n",
    "    def depth(self, root):\n",
    "        if not root: return 0\n",
    "        return max(self.depth(root.left), self.depth(root.right)) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:        \n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def depth(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "\n",
    "            l = depth(root.left)\n",
    "            if l == -1:    # 左子节点不平衡 \n",
    "                return -1\n",
    "            r = depth(root.right)\n",
    "            if r == -1:     # 右子节点不平衡 \n",
    "                return -1\n",
    "            if abs(l-r) > 1:\n",
    "                return -1\n",
    "\n",
    "            return max(l, r) + 1\n",
    "\n",
    "        return False if depth(root) == -1 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        \n",
    "        def height(root):\n",
    "            if root:\n",
    "                hr, hl = height(root.right), height(root.left)\n",
    "                if hr == -1 or hl == -1:\n",
    "                    return -1\n",
    "                if abs(hr-hl) <= 1:\n",
    "                    return max(hr, hl)+1\n",
    "                else:\n",
    "                    return -1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        return False if height(root)==-1 else True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        # def dfs(node):\n",
    "        #     if not node: return 0\n",
    "        #     return 1 + max(dfs(node.left), dfs(node.right))\n",
    "        # def ifBalance(node):\n",
    "        #     if not node: return True\n",
    "        #     if abs(dfs(node.left) - dfs(node.right)) > 1: return False\n",
    "        #     return ifBalance(node.left) and ifBalance(node.right)\n",
    "        # return ifBalance(root)\n",
    "\n",
    "        def recur(root):\n",
    "            if not root: return 0\n",
    "            left = recur(root.left)\n",
    "            if left == -1: return -1\n",
    "            right = recur(root.right)\n",
    "            if right == -1: return -1\n",
    "            return max(left, right) + 1 if abs(left - right) <= 1 else -1\n",
    "\n",
    "        return recur(root) != -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        return self.tryDepth(root, 1)\n",
    "\n",
    "    def tryDepth(self, node: TreeNode, layer: int) -> (bool, int):\n",
    "        if node is None and layer <= 1:\n",
    "            return True\n",
    "        elif node is None:\n",
    "            return True, layer - 1\n",
    "        if not node.left and not node.right and layer <= 1:\n",
    "            return True\n",
    "        if not node.left and not node.right:\n",
    "            return True, layer\n",
    "        b, left_layer = self.tryDepth(node.left, layer + 1)\n",
    "        b2, right_layer = self.tryDepth(node.right, layer + 1)\n",
    "        if layer <= 1:\n",
    "            return abs(left_layer - right_layer) <= 1 and b and b2\n",
    "        else:\n",
    "            return abs(left_layer - right_layer) <= 1 and b and b2, max(left_layer, right_layer)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        return self.tryDepth(root, 1)\n",
    "\n",
    "    def tryDepth(self, node: TreeNode, layer: int) -> (bool, int):\n",
    "        if node is None and layer <= 1:\n",
    "            return True\n",
    "        elif node is None:\n",
    "            return True, layer - 1\n",
    "        elif not node.left and not node.right:\n",
    "            if layer <= 1:\n",
    "                return True\n",
    "            else:\n",
    "                return True, layer\n",
    "        b, left_layer = self.tryDepth(node.left, layer + 1)\n",
    "        b2, right_layer = self.tryDepth(node.right, layer + 1)\n",
    "        if layer <= 1:\n",
    "            return abs(left_layer - right_layer) <= 1 and b and b2\n",
    "        else:\n",
    "            return abs(left_layer - right_layer) <= 1 and b and b2, max(left_layer, right_layer)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def shendu(root, bian):\n",
    "            if not root:\n",
    "                return 0, bian\n",
    "            root_left, bian_left = shendu(root.left, bian)\n",
    "            root_right, bian_right = shendu(root.right, bian)\n",
    "            if abs(root_left-root_right) > 1 or not bian_left or not bian_right:\n",
    "                bian = False\n",
    "                \n",
    "                \n",
    "            \n",
    "            return max(root_left, root_right) + 1, bian\n",
    "        if not root:\n",
    "            \n",
    "            return True\n",
    "        print(shendu(root.left, True))\n",
    "        print(shendu(root.right, True))\n",
    "        \n",
    "        return shendu(root, True)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def balanced(r, curr_len):\n",
    "            if not r:\n",
    "                return True, curr_len\n",
    "            curr_len += 1\n",
    "            left_balanced, len_l = balanced(r.left, curr_len)\n",
    "            if not left_balanced:\n",
    "                return False, 0\n",
    "            right_balanced, len_r = balanced(r.right, curr_len)\n",
    "            if not right_balanced:\n",
    "                return False, 0\n",
    "            if abs(len_l - len_r) <= 1:\n",
    "                return True, max(len_l, len_r)\n",
    "            return False, 0\n",
    "        b, height = balanced(root, 0)\n",
    "        return b\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cache = {}\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "        def depth(node):\n",
    "            if node in self.cache: return self.cache[node]\n",
    "            if not node: return 0\n",
    "            if not node.left and not node.right: return 1\n",
    "            ld = depth(node.left)\n",
    "            rd = depth(node.right)\n",
    "            self.cache[node] = max(ld, rd) + 1\n",
    "            return self.cache[node]\n",
    "        \n",
    "        return abs(depth(root.left)-depth(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def depth(root):\n",
    "            if not root: return 0\n",
    "            if not root.left and not root.right: return 1\n",
    "            return max(depth(root.left),depth(root.right))+1\n",
    "        \n",
    "        if not root: return True\n",
    "        if not root.left and not root.right: return True\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right) and abs(depth(root.left) - depth(root.right)) <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root):\n",
    "            \n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left),height(root.right))+1     \n",
    "        if not root:\n",
    "            return True\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right) and abs(height(root.left)-height(root.right))<=1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            left=dfs(root.left)\n",
    "            right=dfs(root.right)\n",
    "\n",
    "            return max(left,right)+1\n",
    "        if not root:\n",
    "            return True        \n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right) and abs(dfs(root.left)-dfs(root.right))<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            queue=[root]\n",
    "            res=0\n",
    "            while queue:\n",
    "                tmp=[]\n",
    "                for node in queue:\n",
    "                    if node.left:tmp.append(node.left)\n",
    "                    if node.right:tmp.append(node.right)\n",
    "                queue=tmp\n",
    "                res+=1\n",
    "            return res\n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right) and abs(height(root.left)-height(root.right))<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def recur(root):\n",
    "            if not root: return 0\n",
    "            left = recur(root.left)\n",
    "            if left == -1: return -1\n",
    "            right = recur(root.right)\n",
    "            if right == -1: return -1\n",
    "            return max(left, right) + 1 if abs(left - right) <= 1 else -1\n",
    "        \n",
    "        \n",
    "        return recur(root) != -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# 优化点在于不需要重复计算包括不平衡子树的树的高度，一旦左或右有一个不平衡，直接往上返回一个特定值\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        # if not root: return True\n",
    "        # def dfs(root):\n",
    "        #     if not root: return 0\n",
    "        #     return max(dfs(root.left), dfs(root.right)) + 1\n",
    "\n",
    "        # return abs(dfs(root.left) - dfs(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "        def recur(root):\n",
    "            if not root: return 0\n",
    "            left = recur(root.left)\n",
    "            if left == -1: return -1\n",
    "            right = recur(root.right)\n",
    "            if right == -1: return -1\n",
    "            return max(left, right) + 1 if abs(left-right) <= 1 else -1\n",
    "\n",
    "        return recur(root) != -1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(node):\n",
    "            if not node: return 0\n",
    "            left_h = recur(node.left)\n",
    "            if left_h == -1: return -1\n",
    "            right_h = recur(node.right)\n",
    "            if right_h == -1: return -1\n",
    "            return max(left_h, right_h) + 1 if abs(left_h - right_h) <= 1 else -1\n",
    "        return True if recur(root) != -1 else False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            if l == -1 or r == -1 or abs(l - r) > 1:\n",
    "                return -1\n",
    "            return 1 + max(l, r)\n",
    "\n",
    "        return dfs(root) != -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root: return True\n",
    "        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \\\n",
    "            self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n",
    "    def depth(self, root):\n",
    "        if not root: return 0\n",
    "        return max(self.depth(root.left), self.depth(root.right)) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calDepth(self, root):\n",
    "        if not root: \n",
    "            return 0\n",
    "        else:\n",
    "            return max(self.calDepth(root.left), self.calDepth(root.right)) + 1\n",
    "        \n",
    "\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root: \n",
    "            return True\n",
    "        else:\n",
    "            if abs(self.calDepth(root.left)-self.calDepth(root.right))<=1 \\\n",
    "                and self.isBalanced(root.left) and self.isBalanced(root.right):\n",
    "                return True\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0, True\n",
    "            \n",
    "            lh, lis = dfs(root.left)\n",
    "            rh, ris = dfs(root.right)\n",
    "\n",
    "            return (max(lh, rh)+1), (lis and ris and (abs(lh-rh)<2))\n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(root):\n",
    "            if not root:return 0\n",
    "            left = recur(root.left)\n",
    "            if left == -1:return -1\n",
    "            right = recur(root.right)\n",
    "            if right == -1:return -1\n",
    "            return max(left,right)+1 if abs(left-right) <=1 else -1\n",
    "\n",
    "        return recur(root) != -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "   # Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not root: return True\n",
    "        if (abs(self.height(root.left) - self.height(root.right)) > 1):\n",
    "            return False\n",
    "        else:\n",
    "            return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "    def height(self,root):\n",
    "        if not root: return 0\n",
    "        return 1+max(self.height(root.left),self.height(root.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        ans = True\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return 0\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            if abs(l - r) > 1:\n",
    "                ans = False\n",
    "            return max(l, r) + 1\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        self.flag = True\n",
    "        self.dfs(root)\n",
    "        return self.flag\n",
    "    def dfs(self, node):\n",
    "        if self.flag and node is not None:\n",
    "            left = self.dfs(node.left)\n",
    "            right = self.dfs(node.right)\n",
    "            if abs(left-right) > 1:\n",
    "                self.flag = False\n",
    "            return max(left, right)+1\n",
    "        else:\n",
    "            return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        #high = 0\n",
    "        bool = True\n",
    "        def digui(root,high):\n",
    "            nonlocal bool\n",
    "            if not root:\n",
    "                return high\n",
    "            else:\n",
    "                high_left = digui(root.left,high+1)\n",
    "                high_right = digui(root.right,high+1)\n",
    "                if abs(high_left-high_right)>1:\n",
    "                    bool = False\n",
    "                return max(high_left,high_right)\n",
    "        digui(root,1)\n",
    "        return bool\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
